/**
 * 作者：吴超
 * 邮箱：wuchao_19931120@163.com
 * 时间：2021-10-11
 * 描述：从一个有序的整数数组中利用二分查找，找到目标数据，并返回下标，如果没找到返回-1;
 *
 * 思路：
 * 1. 注意边界条件
 * 2. mid要加上start进行更新
 * 3. 考虑第一次二分的mid是不是就是等于target
 */

public class BinarySearch {


    // 循环二分查找
    public static int loopSearch(int[] numbs, int target) {

        int mid = numbs.length / 2;
        if (numbs[mid] == target) {
            return mid;
        }
        int start = 0;
        int end = numbs.length - 1;
        while (start <= end) {
            mid = (end - start) / 2 + start;
            if (numbs[mid] == target) {
                return mid;
            } else if (numbs[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    // 递归二分查找
    public static int recursionSearch(int[] numbs, int target, int start, int end){

        int mid = (end - start) / 2 + start;
        if (numbs[mid] == target) {
            return mid;
        }

        if (start >= end) {
            return -1;
        } else if (target > numbs[mid]) {
            return recursionSearch(numbs, target,mid + 1, end);
        } else if (target < numbs[mid]) {
            return recursionSearch(numbs, target, start, mid - 1);
        }
        return -1;

        }



    public static void main(String[] args) {
//        int[] nus = {3, 5, 11, 17, 21, 23, 28, 30, 32, 50, 64, 78, 81, 95, 101};
        int[] nus = {5};
        System.out.println(loopSearch(nus, 5));
        System.out.println(recursionSearch(nus,5, 0 , nus.length));
    }


}
